package 面试经典150题.链表;

import common.ListNode;
/*    这道题我们需要维护两个子链表lessList和noLessList，分别维护值小于x的节点和值不小于x的节点。
    我们依次遍历原链表的每个节点，如果当前节点小于x，就追加到子链表lessList之后；否则追加到子链表noLessList之后。
    最后拼接两个子链表，noLessList拼接到lessList之后，同时nolessList的最后一个节点为新链表的最后一个节点，其next应该指向空。

    作者：画图小匠
    链接：https://leetcode.cn/problems/partition-list/solutions/2413292/javapython3cshuang-zhi-zhen-mo-ni-wei-hu-5lau/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/

public class T86分隔链表 {
    public ListNode partition(ListNode head, int x) {
        //维护两个链表，分别用来保存小于x的数 和 不小于x的数
        ListNode lessList=new ListNode();
        ListNode noLessList=new ListNode();
        ListNode p=lessList;
        ListNode q=noLessList;
        //遍历链表
        while (head!=null){
            if(head.val<x){
                p.next=head;
                p=p.next;
            }else {
                q.next=head;
                q=q.next;
            }
            head=head.next;
        }
        //把两个链表链接起来
        //保存大于x的的链表最后一个节点的下一个节点应该指向null
        q.next=null;
        p.next=noLessList.next;
        return lessList.next;
    }

}

